package com.zhugang.week12;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program algorithms
 * @description: pairSums
 * @author: chanzhugang
 * @create: 2022/09/06 18:11
 */
public class PairSums {

    /**
     * 面试题 16.24 数对和
     *
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> pairSums(int[] nums, int target) {
        // 数组中找两个数和为target，返回所有整数对
        // 双指针i、j
        // 先排序
        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);
        int i = 0;
        int j = nums.length - 1;
        while (i < j) {
            if (nums[i] + nums[j] == target) {
                List<Integer> list = new ArrayList<>();
                list.add(nums[i]);
                list.add(nums[j]);
                result.add(list);
                i++;
                j--;
            } else if (nums[i] + nums[j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return result;
    }
}